
\subsection{图是怎么存的？}

\subsubsection{直接存边}

什么意思呢？我们开一个数组，数组里每个元素是图的一条边。

这样做有个缺点，每次想要知道两个点之间是否有连边（或者说一条边是否存在），都需要在数组里进行一番查找。而且如果没有对边事先排序的话，就不能使用二分查找的方法（$O(\log n)$），而是每次只能按顺序找（$O(n)$），成本较高。

什么时候会用到这个方法呢？最简单的一个例子是使用 Kruskal 算法求  最小生成树  的时候。

\subsubsection{邻接矩阵}

邻接矩阵的英文名是 adjacency matrix。它的形式是 \texttt{bool adj[n][n]}，这里面 $n$ 是节点个数，$adj[i][j]$ 表示 $i$ 和 $j$ 之间是否有边。

如果边有权值，也可以直接用 \texttt{int adj[n][n]}，直接把边权存进去。

它的优点是可以在 $O(1)$ 时间内得到一条边是否存在，缺点是需要占用 $O(n^2)$ 的空间。对于一个稀疏的图（边相对于点数的平方比较少）来说，用邻接矩阵来存的话，成本偏高。

\subsubsection{邻接表}

邻接表英文名是 adjacency list。它的形式是 \texttt{vector adj[n]}，用 \texttt{adj[i]} 存以 $i$ 为起点的边。

用 \texttt{vector} 无法科学地删除，所以常用 \texttt{list} 实现。

它的特点是可以用来按顺序访问一个结点的出边（或者入边）。

\subsubsection{前向星}

为什么它搜不到英文名呢？因为是中国玩家乱搞出来的。

首先介绍一下链式前向星，本质上是用单向链表实现的邻接表。

形式上是一个结构体：\texttt{struct edge \{edge *pre, int to;\} *head[N], edge[M]}

这个结构广泛出现于算法竞赛选手的代码中，编写简洁而且对于大多数题目效率足够高。

其中 \texttt{head[i]} 用来存以 $i$ 为起点的边，\texttt{edge} 数组是边表。

那么什么是前向星呢？事先把 \texttt{edge} 数组排个序即可。这里可以使用  基数排序  做到 $O(m)$。

\subsection{一些跟图有关的定义}

\subsubsection{路径}

path，是指一个边的序列，其中的边首尾相连。

\subsubsection{简单路径}

simple path，是每条边只经过了一次的路径。

\subsubsection{回路}

cycle，也称为 \texttt{环}，是起点和终点相同的路径。

\subsubsection{简单回路}

图的定点序列中，除了起点和终点相同外，其余顶点不重复的回路。

\subsubsection{连通}

\paragraph{两个点连通}

无向图中点 $u$ 和 $v$ 连通是指存在一条 $u$ 到 $v$ 的路径。

\paragraph{图连通}

如果无向图 $G$ 中任意两个节点连通，称其为是连通的。

\subsubsection{可达}

有向图中点 $u$ 到 $v$ 可达是指存在一条 $u$ 到 $v$ 的路径。

\subsubsection{ 强连通 }

有向图 $G$ 强连通是指，$G$ 中任意两个节点连通。

\subsubsection{ 弱连通 }

有向图 $G$ 弱连通是指，$G$ 中的所有边替换为无向边后，$G$ 为连通图。

\subsubsection{子图}

选取一个节点的子集和边的子集构成的图。

\paragraph{生成子图}

选取的子图的节点和原图一样。

\paragraph{导出子图}

选取一个节点的子集，再选取这些节点相关联的边的集合构成的图。

\paragraph{边导出子图}

选取一个边的子集，再选取这些边相关联的节点的集合，构成的图。

\paragraph{连通子图}

（一个无向图的）连通的子图。

\paragraph{连通分量}

（一个无向图的）极大的连通子图。

【注】：极大是指添加任何节点或者边后都不再满足。

\subsubsection{稀疏图}

$m = \Theta(n)$ 的图，或者指 $m$ 相对较小的图。

\subsubsection{稠密图}

$m = \Theta(n^2)$ 的图，或者指 $m$ 相对较大的图。

\subsubsection{完全图}

$m = \frac{n(n-1)}{2}$ 的简单无向图。

\subsubsection{路径的长度}

一般来说，路径的长度在数值上等于路径的边数，或者如果边是带权的，则是路径的边权和。

\subsubsection{ 最短路径 }

两个节点之间，长度最小的路径。

【注】：不一定存在，不一定唯一。
